// copyright:no copyright,use it if you like
// license boilerplate:maybe BSD
// filename:PriorityQueue.h
// author:Tempest(https://gitee.com/Tempest56890)
// date:2021-11-01
// brief:implement the function of PriorityQueue


#ifndef __TEMPEST_PRIORITYQUEUE__
#define __TEMPEST_PRIORITYQUEUE__

#include <vector>
#include <iostream>

template <typename Unique,typename Comparable>
class PriorityQueue {
public:
    struct DataBase {
        Unique key;
        Comparable data;
        DataBase(const Unique & _k,const Comparable & _d) : key(_k),data(_d) {};
    };
public:
    // basic functions.
    PriorityQueue() : root(nullptr) {};
    PriorityQueue(const PriorityQueue & rhs) : root(nullptr) {
        root=clone(rhs.root);
    };
    ~PriorityQueue() {
        makeEmpty();
    };
    // judge if pq is empty.
    bool isEmpty() const {
        return root==nullptr;
    };
    // i/o param:(none)
    // return:the smallest data.
    const Comparable & findMin() const {
        if (root==nullptr) {
            std::cerr<<"Empty PQ."<<std::endl;
            exit(-1);
        }
        else
            return root->value.data;
    };
    // i/o param:_x
    // function call _merge().
    // insert a data set of key&data
    void insert(DataBase & _x) {
        root=_merge(root,new DataNode(_x,nullptr,nullptr,nullptr,0));
    };
    // i/o param:(none)
    // function call _merge().
    // delete the smallest data of root.
    void deleteMin() {
        DataNode * rt=root;
        if (root==nullptr)
            return;
        else {
            root=_merge(root->left,root->right);
            if (root!=nullptr) root->up=nullptr;
            delete rt;
        }
    };
    // i/o param:(none)
    // function call reclainMemory().
    // clear the pq.
    void makeEmpty() {
        reclaimMemory(root);
    };
    // i/o param:_input
    // function call reclaimMemory()/insert().
    // insert a data set of key&data.
    void buildHeap(std::vector<DataBase> & _input) {
        if (root!=nullptr)
            reclaimMemory(root);
        for (int i=0;i<_input.size();++i) {
            insert(_input[i]);
        }
    };
    // i/o param:k
    // function call remove().
    // delete the datanode with key k.
    // if nonexist key k, do nothing.
    void remove(Unique k) {
        remove(k,root);
    };
    // i/o param:k/d
    // function call modifyData().
    // modify d to the datanode with key k
    // if nonexist key k, do nothing.
    void modifyData(Unique k,Comparable d) {
        modifyData(k,d,root);
    };
    // i/o param:rhs
    // function call _merge().
    // merge rhs to pq
    // clear rhs.
    void merge(PriorityQueue & rhs) {
        if (this==&rhs)
            return;
        root=_merge(root,rhs.root);
        rhs.root=nullptr;
    };
    // i/o param:rhs
    // function call reclaimMemory()/clone().
    // rebuild operator function.
    const PriorityQueue & operator=(const PriorityQueue & rhs) {
        if (this!=&rhs) {
            reclaimMemory(root);
            root=clone(rhs.root);
        }
        return * this;
    };
private:
    struct DataNode {
        DataBase value;
        DataNode * left;
        DataNode * right;
        DataNode * up;
        int npl;
        DataNode(DataBase & _v,
                 DataNode * l=nullptr,DataNode * r=nullptr,
                 DataNode * u=nullptr,int _npl=0)
        : value(_v),left(l),right(r),up(u),npl(_npl) {};
    };
    DataNode * root;
    // i/o param:_h1,_h2
    // function call __merge().
    // makes sure _h1->value.data<_h2->value.data
    DataNode * _merge(DataNode * _h1,DataNode * _h2) {
        if (_h1==nullptr)
            return _h2;
        else if (_h2==nullptr)
            return _h1;
        else {
            if (_h1->value.data<_h2->value.data)
                return __merge(_h1,_h2);
            else
                return __merge(_h2,_h1);
        }
    };
    // i/o param:_h1,_h2
    // function call _merge().
    // already assume that _h1->data < _h2->data
    DataNode * __merge(DataNode * _h1,DataNode * _h2) {
        if (_h1->left==nullptr) {
            _h1->left=_h2;
            _h2->up=_h1;
        }
        else {
            _h1->right=_merge(_h1->right,_h2);
            if (_h1->right!=nullptr)
                _h1->right->up=_h1;
            if(_h1->right!=nullptr && _h1->left->npl<_h1->right->npl)
                swapChild(_h1);
            if (_h1->right==nullptr)
                _h1->npl=0;
            else
                _h1->npl=_h1->right->npl+1;
        }
        return _h1;
    };
    // i/o param:k,t
    // function call findKey()/_merge()/npl_reorient().
    void remove(Unique k,DataNode * t) {
        DataNode * rt=findKey(k,t);
        if (rt==nullptr)
            return;
        else {
            if (rt==root) {
                root=_merge(root->left,root->right);
                root->up=nullptr;
            }
            else if (rt==rt->up->left) {
                rt->up->left=_merge(rt->left,rt->right);
                if (rt->up->left!=nullptr) rt->up->left->up=rt->up;
            }
            else {
                rt->up->right=_merge(rt->left,rt->right);
                if (rt->up->right!=nullptr) rt->up->right->up=rt->up;
            }
            npl_reorient(root);
            delete rt;
        }
    };
    // i/o param:k,t
    // function call findKey()/_merge()/npl_reorient().
    void modifyData(Unique k,Comparable d,DataNode * t) {
        DataNode * rt=findKey(k,t);
        if (rt==nullptr)
            return;
        else {
            Comparable old=rt->value.data;
            if (rt==root) {
                root=_merge(root->left,root->right);
                root->up=nullptr;
            }
            else if (rt==rt->up->left) {
                rt->up->left=_merge(rt->left,rt->right);
                if (rt->up->left!=nullptr) rt->up->left->up=rt->up;
            }
            else {
                rt->up->right=_merge(rt->left,rt->right);
                if (rt->up->right!=nullptr) rt->up->right->up=rt->up;
            }
            npl_reorient(root);
            DataBase db=* new DataBase(k,old+d);
            insert(db);
            delete rt;
        }
    };
    // i/o param:t
    // function call npl_orient().
    // reclear npl od all datanodes.
    void npl_reorient(DataNode * t) {
        if (t==nullptr)
            return;
        else if (t->left==nullptr || t->right==nullptr) {
            npl_reorient(t->left);
            npl_reorient(t->right);
            t->npl=0;
            if (t->left==nullptr)
                swapChild(t);
        }
        else {
            npl_reorient(t->left);
            npl_reorient(t->right);
            if (t->left->npl<t->right->npl)
                swapChild(t);
            t->npl=t->right->npl+1;
        }
    };
    DataNode * findKey(Unique k,DataNode * t) {
        if (t==nullptr)
            return nullptr;
        else if (t->value.key==k)
            return t;
        else {
            DataNode * rt=findKey(k,t->left);
            if (t==nullptr)
                rt=findKey(k,t->right);
            return rt;
        }
    };
    // i/o param:t
    // swap left child with
    // right child of datanode t.
    void swapChild(DataNode * t) {
        DataNode * rt=t->left;
        t->left=t->right;
        t->right=rt;
    };
    // i/o param:t
    // function call reclaimMemory().
    // recursely clear all datanodes
    // including t and datanodes under it.
    void reclaimMemory(DataNode * t) {
        if (t!=nullptr) {
            if (t->left!=nullptr) reclaimMemory(t->left);
            if (t->right!=nullptr) reclaimMemory(t->right);
            t=nullptr;
        }
    };
    // i/o param:t
    // function call DataNode().
    // deep clone.
    DataNode * clone(DataNode * t) const {
        if (t==nullptr)
            return nullptr;
        return new DataNode(t->value,clone(t->left),clone(t->right),t->up,t->npl);
    };
};


#else
#endif
